//////////////////////////////////////////////////////////
//
//	File: main.cpp
//	Version 1.0
//	Authors: Adam Couch, Victoria Sater
//  Description: Obtains name and difficulty level
//		from user, then applies either a basic heuristic
//		or MiniMax function to allow the user to play
//		against a computer opponent
//
//////////////////////////////////////////////////////////

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include "board.h"

using namespace std;

//#define SKIP_INTRO			// uncomment this line to skip intro questions
//#define SHOW_MIN_MAX_TREE	// uncomment this line to print out the minmax tree (only recommended for depth limits less than 6
#define SHOW_HEURISTIC		// uncomment this line to show heuristic calculation for each computer turn

int playGame(string name, int difficulty);	// play game of mancala, handle interactions between computer and player
int playerMove();				// ask player to choose their move
int MinMax(vector<Hole> theHoles);							// Core min-max function
int MaxMove(vector<Hole> theHoles, int alpha, int beta);	// Max function, will return computers best move for current game state
int MinMove(vector<Hole> theHoles, int alpha, int beta);	// Min function, will return players best move for current game state

// globals
int depth;				//
int depthLimit = 10;		// depth limit for minmax function (computer starts exponentially slowing down around 10)
int numBranches = 0;	// number of branches in tree
int numPruned = 0;		// number of branches pruned

int main() {

	string name = "Player1";
	string input = "";
	
	int difficulty = 3;

	#ifndef SKIP_INTRO
		cout << "What is your name? ";
		cin >> name;
	#endif

	// track high score

	// for as long as a player wants to play, call kick off function; arguments are (Player Name)
	while (true) {
		string play;
		cout << "\nHi " << name <<" ! Would you like to play a game of mancala? (Y/n) ";
		cin >> play;
		cout << "\n";
		if (play == "Y" || play == "y" || play == "yes" || play == "Yes" || play == "Play" || play == "play") 
		{
			// ask player what difficulty it wants to play
			#ifndef SKIP_INTRO
				bool loop = true;
				while (loop)
				{
					cout << "Enter a number 1-3 for difficulty level: ";
					cin >> input;
					if ( input.size() <=1 ) 
					{
						difficulty = atoi( input.c_str() );
						if ( difficulty >=1 && difficulty  <=3 )
						{
							loop = false;
							if ( difficulty == 1 ) cout << "\nSimple Heuristic Mancala\n";
							if ( difficulty == 2 ) cout << "\nComplex Heuristic Mancala\n";
							if ( difficulty == 3 ) cout << "\nMiniMax with Alpha-Beta Pruning\n";
						}
					}
				}
			#endif

			int result = playGame(name, difficulty);
			if (result == 1)
				cout << "You won! Excellent job!\n";
			else if (result == -1)
				cout << "Sorry.... You lost.\n";
			else if (result == 0)
				cout << "You tied.\n";
		} else {
			cout << "Awwwww! Ok. Bye!\n";
			break;
		}
	}

	system("pause");
	return 0;
}

struct holeOrder {
	int index;
	Hole hole;
};

int playGame(string name, int difficulty) {

    cout << "Computer: \"Hi " << name << "!\"\n";
    Board board;
	bool moveAgain = true;
	int computerMove = 0;
    while(board.endGame() == false)
    {	
		moveAgain = true;
		// players Turn
		while (moveAgain && !board.endGame())
		{
			system("cls");
			cout << "Hole Numbering Scheme:\n";
			board.printDefaultBoard();
			cout << "\nPlayers Move:\n";
			board.printBoard();
			cout << "Please make a move (1-6): ";
			int moveNum;
			string input;
			cin >> input;
			if ( input.size() <=1 ) 
			{
				moveNum = atoi( input.c_str() );
				// check that user input is in range, and did not pick an empty hole
				if (moveNum <= 6 && moveNum >= 1 && board.getHoles().at(moveNum).getNum() != 0 ) 
					moveAgain = board.makeMove(1, moveNum);
			}
		}

		moveAgain = true;
		// computers turn
		while (moveAgain && !board.endGame())
		{
			system("cls");
			cout << "Hole Numbering Scheme:\n";
			board.printDefaultBoard();
			cout << "\nComputers Move:\n";
			board.printBoard();
			//
			// calculate move via Min\max or random function
			//
			if ( difficulty == 1)
				board.calculateSimpleH(); // uses simple, points-only heuristic function
			else
				board.calculateComplexH(); // uses points and new move heuristic function

			priority_queue< pair< int, Hole >, vector< pair< int, Hole > >, Hole::CompH > moves;
			for (int i = 8; i <= 13; ++i) {
				if (board.getHoles()[i].getNum() > 0)
				{
					#ifdef SHOW_HEURISTIC
						cout << "Hole: " << i << ", H: " << board.getHoles()[i].getH() << "\n";
					#endif
					pair< int, Hole > currentHole (i, board.getHoles()[i]);
					moves.push(currentHole);
				}
			}

			if ( difficulty != 3)
			{
				do computerMove = moves.top().first;
				// do computerMove = board.randomMove(); // uncomment to use random move function
				while ( board.getHoles().at(computerMove).getNum() == 0);	
			}
			else
			{
				computerMove = MinMax( board.getHoles() );
				if ( board.getHoles().at(computerMove).getNum() == 0)
				{
					cout << "Min-Max Error: Reverting to basic heuristic\n";
					computerMove = moves.top().first;
				}
			}
			moveAgain = board.makeMove(0, computerMove);
			cout << "\nComputer chooses: " << computerMove << "\t\t( Branches: " << numBranches << ", Pruned: " << numPruned << " )\n";
			system("pause");
		}
    }
	board.printBoard();
    if ( board.getHoles().at(7).getNum() > board.getHoles().at(0).getNum() )
		return 1;
	else if ( board.getHoles().at(7).getNum() == board.getHoles().at(0).getNum() )
		return 0;
	else return -1;
}

//////////MIN-MAX Functions////////////////

// Core Min-Max function, will return the computers best over-all move
int MinMax(vector<Hole> theHoles)
{
	depth = 0;
	numBranches = 0;
	numPruned = 0;
	#ifdef SHOW_MIN_MAX_TREE
		cout << "Starting MinMax\n";
	#endif
	return MaxMove(theHoles, 999, -999);
}

// Max function, will return computers best move for current game state
int MaxMove(vector<Hole> theHoles, int alpha, int beta)
{
	depth++;
	numBranches++;
	Board tempBoard(theHoles);
	vector<int> moves = tempBoard.possibleMoves(0);	// possible moves for computer
	int bestMove;
	if (!moves.empty()) bestMove = moves[0];
	int move = 0;
	int valueOfBestMove = 0;
	int valueOfMove = 0;
	
	// check if game has ended, or if depth has exceeded depthLimit
	if ( tempBoard.endGame() || depth > depthLimit )
	{
		#ifdef SHOW_MIN_MAX_TREE
			for (int i=0; i< depth; i++) cout<<"\t";
			cout << "Max: " << tempBoard.evaluateGame( theHoles, 0) << "\n";
		#endif
		depth--;
		return tempBoard.evaluateGame( theHoles, 0);
	}
	else 
	{	
		//for (size_t i=moves.size(); i > 0; i--)
		for (size_t i=0; i < moves.size(); i++)
		{
			valueOfMove = 0;
			valueOfBestMove = 0;
			tempBoard.setHoles(theHoles);

			// make the move
			if ( tempBoard.makeMove(0,moves[i]) )	// makeMove returned true, move again
			{
				move = MaxMove( tempBoard.holes, alpha, beta );	// Max moves again
				if ( move > 7 && move <= 13 )		// non-terminal move
				{
					// calculate value of the move
					tempBoard.makeMove(0,move);
					tempBoard.calculateComplexH();
					valueOfMove = tempBoard.getValue(0);
				}
				else valueOfMove = move;			// terminal (end of game) value
			}
			else
			{
				move = MinMove( tempBoard.holes, alpha, beta );	// Min makes move
				if ( move > 0 && move < 7 )			// non-terminal move
				{
					// calculate value of the move
					tempBoard.makeMove(1,move);
					tempBoard.calculateComplexH();
					valueOfMove = tempBoard.getValue(0);
				}
				else valueOfMove = move;			// terminal (end of game) value
			}

			// calculate value of best move
			tempBoard.setHoles(theHoles);
			tempBoard.makeMove(0,bestMove);
			tempBoard.calculateComplexH();
			valueOfBestMove = tempBoard.getValue(0);

			// compare move and best move
			if ( valueOfMove > valueOfBestMove )
			{
				bestMove = moves[i];
				alpha = valueOfMove;
			}
			// check alpha beta values, prune branch if necessary
			if ( beta > alpha )
			{
				#ifdef SHOW_MIN_MAX_TREE
					for (int j=0; j< depth; j++) cout<<"\t";
					cout << "Max: i= "<< i << " m= " << bestMove << "\t" << valueOfBestMove << "\t(" << alpha << "," << beta << ")\n";
				#endif
				depth--;
				numPruned++;
				return bestMove;
			}
		}			
	}
	#ifdef SHOW_MIN_MAX_TREE
		for (int i=0; i< depth; i++) cout<<"\t";
		cout << "Max: " << bestMove << "\t" << valueOfBestMove << "\t(" << alpha << "," << beta << ")\n";
	#endif
	depth--;
	return bestMove;
}

// Min function, will return players best move for current game state
int MinMove(vector<Hole> theHoles, int alpha, int beta)
{
	depth++;
	numBranches++;
	Board tempBoard(theHoles);
	vector<int> moves = tempBoard.possibleMoves(1);		// possible moves for human
	int bestMove;
	if (!moves.empty()) bestMove = moves[0];
	int move = 0;
	int valueOfBestMove = 0;
	int valueOfMove = 0;

	// check if game has ended, or if depth has exceeded depthLimit
	if ( tempBoard.endGame() || depth > depthLimit )
	{
		#ifdef SHOW_MIN_MAX_TREE
			for (int i=0; i< depth; i++) cout<<"\t";
			cout << "Min: " << tempBoard.evaluateGame( theHoles, 1) << "\n";
		#endif
		depth--;
		return tempBoard.evaluateGame( theHoles, 1);
	}
	else 
	{	
		//for (size_t i=moves.size(); i > 0; i--)
		for (size_t i=0; i < moves.size(); i++)
		{
			valueOfMove = 0;
			valueOfBestMove = 0;
			tempBoard.setHoles(theHoles);

			// make the move
			if ( tempBoard.makeMove(1,moves[i]) )	// makeMove returned true, move again
			{
				move = MinMove( tempBoard.holes, alpha, beta );	// Min moves again
				if ( move > 0 && move < 7 )			// non-terminal move
				{
					// calculate value of the move
					tempBoard.makeMove(1,move);
					tempBoard.calculateComplexH();
					valueOfMove = tempBoard.getValue(1);
					//valueOfMove = tempBoard.holes[move].getH();
				}
				else valueOfMove = move;			// terminal (end of game) value
			}
			else
			{
				move = MaxMove( tempBoard.holes, alpha, beta );	// Max makes move
				if ( move > 7 && move <= 13 )		// non-terminal move
				{
					// calculate value of the move
					tempBoard.makeMove(0,move);
					tempBoard.calculateComplexH();
					valueOfMove = tempBoard.getValue(1);
				}
				else valueOfMove = move;			// terminal (end of game) value
			}	

			// calculate value of best move
			tempBoard.setHoles(theHoles);
			tempBoard.makeMove(1,bestMove);
			tempBoard.calculateComplexH();
			valueOfBestMove = tempBoard.getValue(1);

			// compare move and best move
			if ( valueOfMove > valueOfBestMove )
			{
				bestMove = moves[i];
				beta = valueOfMove;
			}
			// check alpha beta values, prune branch if necessary
			if ( beta < alpha )
			{
				#ifdef SHOW_MIN_MAX_TREE
					for (int j=0; j< depth; j++) cout<<"\t";
					cout << "Min: i= "<< i << " m= " << bestMove << "\t" << valueOfBestMove << "\t(" << alpha << "," << beta << ")\n";
				#endif
				depth--;
				numPruned++;
				return bestMove;
			}
		}			
	}
	#ifdef SHOW_MIN_MAX_TREE
		for (int i=0; i< depth; i++) cout<<"\t";
		cout << "Min: " << bestMove << "\t" << valueOfBestMove << "\t(" << alpha << "," << beta << ")\n";
	#endif
	depth--;
	return bestMove;
}
